/**
 * 所有函数都只考虑原生的 JavaScript 数组和对象
 * 所有的函数都是纯（Pure）函数。
 * 你可能觉得在函数里区分 Array 和 Object 没必要，因为对于
 * JS 而言 Object 也可以像 Array 一样使用。但我只是不想对代
 * 码做任何假设，也许其他人的代码会区分数组和对象。
 *
 * 命名约定：
 * a 代表 JS 数组
 * o 表示参数既可以是 JS 数组，也可以是 JS 对象
 * fn 期望这个参数是一个函数
 * n 为一个数值
 * r 通常用做返回值
 * i 用作数组的迭代变量
 * k 用作对象的关键字迭代变量
 *
 * 注意：
 * jQuery 中传递给 each 和 map 的函数 fn 参数顺序是相反的，
 * 即 each(o, function(value, key) {});
 * 而 map (o, function(key, value) {});
 * 这无疑给开发者造成记忆负担。因此本例程里所有过滤函数都
 * 统一使用 value, key 的顺序，即：
 * Array[index] = fn(element, index);
 * Object[key] = fn(value, key);
 *
 * 另一个较大的区别是：jQuery 中 map 函数总是返回数组；本
 * 例程中 map 返回结果类型和参数类型一致。
 */

// 函数组合
var complement;
var compose;
var identity;
var constantly;
var partial;

// 过滤器
var seq;
var map;
var each;
var find_if;
var find;
var filter;
var remove;
var distinct;
var keys;
var vals;

// 成员访问
var first;
var second;
var ffirst;
var fsecond;
var nth;
var last;
var butlast;
var rest;
var next;

// 数组操作
var rseq;
var conj;
var cons;
var concat;
var take;
var take_while;
var drop;
var drop_while;
var drop_last;

// 平摊
var apply;
var reduce;
var min;
var max;
var mapcat;
var flatten;
var interleave;
var interpose;

// 分组
var range;
var slice;
var group;
var split_at;
var split_by;
var partition;

// 谓词
var pos;
var neg;
var even;
var odd;
var empty;
var some;
var every;

(function() {
    function is(o, type) {
        return Object.prototype.toString.call(o) == '[object ' + type + ']';
    }

    function isArray(o) {
        return o instanceof Array || is(o, 'Arguments');
    }

    /** == 函数组合 == */

    /*
     * 返回函数 fn 的补函数，即 !fn()
     */
    complement = function(fn) {
        return function() {
            return !apply(fn, arguments);
        };
    };

    /*
     * 按从右往左顺序复合一组函数
     * 比如 compose(a, b, c)(args)
     * 等价于 a(b(c(args)));
     */
    compose = function() {
        var fn = rseq(arguments);
        return function() {
            var r = arguments;
            each(fn, function(e) {
                r = [ apply(e, r) ];
            });
            return first(r);
        };
    };

    identity = function(o) {
        return o;
    };

    constantly = function(o) {
        return function() {
            return o;
        };
    };

    partial = function(fn) {
        var args = rest(arguments);
        return function() {
            return apply(fn, concat(args, arguments));
        };
    };

    /** == 过滤器 == */
    /**
     * 尽力将传入的对象翻译成对应的 JavaScript 对象
     * 和其他函数一样，seq 也是一个纯函数
     */
    seq = function(o) {
        var r = [];
        if (isArray(o)) {
            r = new Array(o.length);
            for (var i = 0; i < o.length; i++) {
                r[i] = o[i];
            }
        } else if (o instanceof Object) {
            for (var k in o) {
                r.push([k, o[k]]);
            }
        } else {
            r = [o];
        }
        return r;
    };

    map = function(o, fn) {
        var r = null;
        if (isArray(o)) {
            r = new Array(o.length);
            for (var i = 0; i < o.length; i++) {
                r[i] = fn(o[i], i);
            }
        } else {
            r = {};
            for (var k in o) {
                r[k] = fn(o[k], k);
            }
        }
        return r;
    };

    each = function(o, fn) {
        if (isArray(o)) {
            for (var i = 0; i < o.length; i++) {
                fn(o[i], i);
            }
        } else {
            for (var k in o) {
                fn(o[k], k);
            }
        }
        return o;
    };

    find_if = function(o, fn) {
        if (isArray(o)) {
            for (var i = 0; i < o.length; i++) {
                if (fn(o[i], i)) {
                    return i;
                }
            }
            return -1;
        } else {
            for (var k in o) {
                if (fn(o[k], k)) {
                    return k;
                }
            }
            return null;
        }
    };

    find = function(o, t) {
        return find_if(o, function(e) {
            return e == t;
        });
    };

    filter = function(o, fn) {
        var r = null;
        if (isArray(o)) {
            r = [];
            for (var i = 0; i < o.length; i++) {
                if (fn(o[i], i)) {
                    r.push(o[i]);
                }
            }
        } else {
            r = {};
            for (var k in o) {
                if (fn(o[k], k)) {
                    r[k] = o[k];
                }
            }
        }
        return r;
    };

    remove = function(o, fn) {
        return filter(o, complement(fn));
    };

    distinct = function(o) {
        var set = {};
        var r = null;
        if (isArray(o)) {
            r = [];
            for (var i = 0; i < o.length; i++) {
                if (!set[o[i]]) {
                    set[o[i]] = true;
                    r.push(o[i]);
                }
            }
        } else {
            r = {};
            for (var k in o) {
                if (!set[o[k]]) {
                    set[o[k]] = true;
                    r[k] = o[k];
                }
            }
        }
        return r;
    };

    keys = function(o) {
        return map(seq(o), function(e) {
            return first(e);
        });
    };

    vals = function(o) {
        return map(seq(o), function(e) {
            return second(e);
        });
    };

    /** == 成员访问 == */

    first = function(a) {
        return a[0];
    };

    second = function(a) {
        return a[1];
    };

    ffirst = function(a) {
        return a[0][0];
    };

    fsecond = function(a) {
        return a[0][1];
    };

    nth = function(a, n) {
        return a[n];
    };

    last = function(a) {
        return a[a.length - 1];
    };

    butlast = function(a) {
        return drop_last(a);
    };

    rest = function(a) {
        var r = seq(a);
        r.shift();
        return r;
    };

    next = function(a) {
        var r = rest(a);
        return r.length == 0? null: r;
    };

    /** == 数组操作 == */

    rseq = function(a) {
        var r = new Array(a.length);
        for (var i = 0; i < a.length; i++) {
            r[i] = a[a.length - i - 1];
        }
        return r;
    };

    conj = function(a) {
        var r = [];
        for (var i = arguments.length - 1; i > 0; i--) {
            r.push(arguments[i]);
        }
        for (var i = 0; i < a.length; i++) {
            r.push(a[i]);
        }
        return r;
    };

    cons = function(item, a) {
        return conj(a, item);
    };

    // 连接数组
    concat = function() {
        var r = [];
        for (var i = 0; i < arguments.length; i++) {
            for (var j = 0; j < arguments[i].length; j++) {
                r.push(arguments[i][j]);
            }
        }
        return r;
    };

    take = function(a, n) {
        return slice(a, 0, n);
    };

    take_while = function(a, fn) {
        return slice(a, 0, find_if(a, complement(fn)));
    };

    drop = function(a, n) {
        return slice(a, n);
    };

    drop_while = function(a, fn) {
        return slice(a, find_if(a, complement(fn)));
    };

    drop_last = function(a, n) {
        if (arguments.length == 1) {
            n = 1;
        }
        if (a.length < n) {
            n = a.length;
        }
        var r = new Array(a.length - n);
        for (var i = 0; i < r.length; i++) {
            r[i] = a[i];
        }
        return r;
    };

    /** == 平摊 == */

    apply = function(fn, args) {
        return fn.apply(null, args);
    };

    reduce = function(a, fn) {
        var r = a[0];
        for (var i = 1; i < a.length; i++) {
            r = fn(r, a[i]);
        }
        return r;
    };

    min = function() {
        return reduce(arguments, function(a, b) {
            return a < b? a: b;
        });
    };

    max = function() {
        return reduce(arguments, function(a, b) {
            return a > b? a: b;
        });
    };

    mapcat = compose(concat, map);

    // 摊平数组，例如 [1, [2, [3, [4]]]] 返回 [1, 2, 3, 4]
    flatten = function(a) {
        var r = [];
        for (var i = 0; i < a.length; i++) {
            if (isArray(a[i])) {
                var sub = flatten(a[i]);
                for (var j = 0; j < sub.length; j++) {
                    r.push(sub[j]);
                }
            } else {
                r.push(a[i]);
            }
        }
        return r;
    };

    interleave = function() {
        var size = apply(min, map(arguments, function(v) {
            return v.length;
        }));
        var r = [];
        for (var i = 0; i < size; i++) {
            for (var j = 0; j < arguments.length; j++) {
                if (i < arguments[j].length) {
                    r.push(arguments[j][i]);
                }
            }
        }
        return r;
    };

    interpose = function(a, sep) {
        if (a.length == 0) {
            return [];
        }

        var r = new Array(a.length * 2 - 1);
        each(a, function(e, i) {
            r[i * 2] = e;
            if (i > 0) {
                r[i * 2 - 1] = sep;
            }
        });
        return r;
    };

    /** == 分组 == */

    range = function() {
        var start = arguments.length == 1? 0: arguments[0];
        var stop = arguments[arguments.length == 1? 0: 1];
        var step = arguments.length < 3? 1: arguments[2];

        var a = [];
        if (start < stop && step > 0) {
            for (var i = start; i < stop; i += step) {
                a.push(i);
            }
        } else if (start > stop && step < 0) {
            for (var i = start; i > stop; i += step) {
                a.push(i);
            }
        }
        return a;
    };

    slice = function(a, start, stop, step) {
        if (arguments.length < 2) {
            start = 0;
        }
        if (arguments.length < 3) {
            stop = a.length;
        }
        if (arguments.length < 4) {
            step = start < stop? 1: -1;
        }

        var r = [];
        if (start < stop && step > 0) {
            for (var i = start; i < stop && i < a.length; i += step) {
                r.push(a[i]);
            }
        } else if (start > stop && step < 0) {
            for (var i = start; i > stop && i >= 0; i += step) {
                r.push(a[i]);
            }
        }
        return r;
    };

    group = function(a, fn) {
        var r = {};
        each(a, function(e, i) {
            var key = fn(e, i);
            if (!r[key]) {
                r[key] = [];
            }
            r[key].push(e);
        });
        return r;
    };

    split_at = function(a, n) {
        return [slice(a, 0, n), slice(a, n)];
    };

    split_by = function(a, fn) {
        return split_at(a, find_if(a, complement(fn)));
    };

    partition = function(a, step, pad) {
        if (arguments.length < 2 || !pos(step)) {
            return [];
        }
        if (arguments.length < 3) {
            pad = step;
        }
        var r = [];
        for (var i = 0; i + step <= a.length; i += pad) {
            r.push(slice(a, i, i + step));
        }
        return r;
    };

    /** == 谓词 == */
    pos = function(n) {
        return n > 0;
    };

    neg = function(n) {
        return n < 0;
    };

    even = function(n) {
        return n % 2 == 0;
    };

    odd = function(n) {
        return n % 2 != 0;
    };

    some = function(o, fn) {
        var r = find_if(o, fn);
        return r != null && r != -1;
    };

    every = function(o, fn) {
        return !some(o, complement(fn));
    };

    empty = function(o) {
        return !some(o, constantly(true));
    };
})();